/**
 * 方阵，每走到一格，就减去当前格的权值 
 * 问能否从左上走到右下
 * 就是求最短路径，规模很小，用队列即可
 */
class Solution {

using vi = vector<int>;
using pii = pair<int, int>;

int N;
int M;
vector<vi> D;

public:
    bool findSafeWalk(vector<vector<int>>& grid, int health) {
        int const INF = 100000;
        N = grid.size();
        M = grid[0].size();
        D.assign(N, vi(M, 0));
        D[0][0] = health - grid[0][0];

        vector<pii> O {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1}
        };
        vector<vi> Flag(N, vi(M, 0));
        queue<pii> q;
        q.push({0, 0});
        Flag[0][0] = 1;

        while(not q.empty()){
            auto h = q.front(); q.pop();
            Flag[h.first][h.second] = 0;

            for(const auto & o : O){
                int nr = h.first + o.first;
                int nc = h.second + o.second;
                if(0 <= nr and nr < N and 0 <= nc and nc < M){
                    int tmp = D[h.first][h.second] - grid[nr][nc];
                    if(tmp > D[nr][nc]){
                        D[nr][nc] = tmp;
                        if(not Flag[nr][nc]){
                            q.push({nr, nc});
                            Flag[nr][nc] = 1;
                        }
                    }
                }
            }
        }

        return D[N - 1][M - 1] > 0;
    }
};